from functools import cache


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n = len(s)
        m = len(p)

        # 当前操作作为最终状态，考虑怎么递归到前一个状态
        @cache
        def dfs(i, j):

            if i < 0:
                # 正常情况匹配完全
                if j < 0:
                    return True
                # 有 * 的情况
                if p[j] != "*":
                    return False
                # 有 * , 匹配多个的情况,把j递归到 j<0,如果中途有一个 不等于 * 返回False，匹配 空字符
                return dfs(i, j - 2)
            if j < 0 and i >= 0:
                return False

            # 先匹配简单的
            # 匹配单个字符
            if s[i] == p[j] or p[j] == ".":
                return dfs(i - 1, j - 1)
            # 复杂的匹配
            elif p[j] == "*":
                # 可以匹配 0个 单个 多个(三个，四个。。。)前面的字符
                zero=dfs(i,j-2)
                if s[i]==p[j-1] or p[j-1]==".":
                    more=dfs(i-1,j)
                    return zero or more
                return zero
            # 不匹配
            else:
                return False

        # 最终状态
        return dfs(n - 1, m - 1)